/*
Copyright (c) [2019年5月1日] [吴超]
[MBT_studio] is licensed under Mulan PSL v2.
You can use this software according to the terms and conditions of the Mulan PSL v2.
You may obtain a copy of Mulan PSL v2 at:
		 http://license.coscl.org.cn/MulanPSL2
THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
See the Mulan PSL v2 for more details.
*/
#include "stdafx.h"
#include "凸包计算.h"

static void f_释放顶点排序数据(void* data) {
	if(data) free(data);
}

static bool on_凸边顶点排序_排序(S_凸边顶点排序元素* d1, S_凸边顶点排序元素* d2) {
	if (d1->角度 < d2->角度) return true;
	return false;
}


uint32 f_graph_计算最大X索引(const vec2* point, uint32 num) {
	float32 maxX = -10000000;
	uint32 maxX_ID = 0;

	for (uint32 i = 0; i < num; ++i) {
		if (point[i].x > maxX) {
			maxX = point[i].x;
			maxX_ID = i;
		}
	}

	return maxX_ID;
}
uint32 f_graph_计算最大Y索引(const vec2* point, uint32 num) {
	float32 maxY = -10000000;
	uint32 maxY_ID = 0;

	/*if (num > 8) {
		__m256 组L = _mm256_set1_ps(1e-7);
		__m256 组R = _mm256_set1_ps(1e-7);

		uint32 组数量 = num / 8;

		uint32 余下数量 = num - 组数量 * 8;
		for (uint32 i = 0; i < 余下数量; ++i) {
			组R.m256_f32[i] = point[组数量 * 8 + i].y;
		}

		for (uint32 j = 0; j < 组数量; ++j) {
			for (uint32 i = 0; i < 8; ++i) {
				组L.m256_f32[i] = point[j * 8 + i].y;
			}

			组R = _mm256_cmp_ps(组L, 组R, _CMP_GT_OS);

			
			for (uint32 i = 0; i < 8; ++i) {
				if (组R.m256_f32[i] > maxY) {
					maxY = 组R.m256_f32[i];
					maxY_ID = 组数量 * j + (7 - i);
				}
			}
			组R = 组L;
		}
	}
	else {
		
	}*/
	for (uint32 i = 0; i < num; ++i) {
		if (point[i].y > maxY) {
			maxY = point[i].y;
			maxY_ID = i;
		}
	}

	return maxY_ID;
}

bool f_面朝向(const vec2& a, const vec2& b, const vec2& c) {
	vec2 ab = { b.x - a.x, b.y - a.y };
	vec2 bc = { c.x - b.x, c.y - b.y };
	//vec_normalize(&ab);
	//vec_normalize(&bc);
	//if(vec_dot(ab, bc) <= -1) return true;
	return ab.x * bc.y - ab.y * bc.x >= 0;
}

uint32 f_graph_计算2D凸包(vec2* point, uint32 num, S_凸边顶点* cv) {
	uint32 初始Y顶点ID = f_graph_计算最大Y索引(point, num);
	auto* 排序顶点 = f_core_createList();
	
	vec2 极点 = point[初始Y顶点ID];

	//std::vector<uint32> 重叠顶点索引;
	for (uint32 i = 0; i < num; ++i) {
		point[i].x += 0.002*num;
		point[i].y += 0.002*num;
	}
	vec2 基向量 = vec2{ 1,0 };
	for (uint32 i = 0; i < num; ++i) {
		S_凸边顶点排序元素* 元素 = (S_凸边顶点排序元素*)malloc(sizeof(S_凸边顶点排序元素));
		元素->ID = i;
		if (i != 初始Y顶点ID) {
			vec2 A = vec_normalize(point[i] - 极点);
			if (vec_len(A) > 1e-6) {
				元素->角度 = dot(A, 基向量) + 1.1;
			}
			else {
				元素->角度 = 0;
			}
		}
		else {
			元素->角度 = 4;
		}
		f_core_addListEndItem(排序顶点, 元素);
	}
	
	f_core_list_sort(排序顶点, (fn_list_sort)on_凸边顶点排序_排序);


	uint32 角数量 = num - 2;
	
	for (uint32 i = 0; i < 角数量; ++i) {
		bool 跳出 = true;

		S_ListItem* 当前排序顶点 = 排序顶点->ptr_item;
		while (当前排序顶点) {
			S_ListItem* 中间 = f_core_list_nth(当前排序顶点, 1);
			S_ListItem* 右边 = f_core_list_nth(当前排序顶点, 2);

			if (!中间) {
				//跳出 = true;
				break;
			}
			if (!右边) {
				右边 = 排序顶点->ptr_item;
				//跳出 = true;
				break;
			}

			S_凸边顶点排序元素& a = *((S_凸边顶点排序元素*)当前排序顶点->ptr_userData);
			S_凸边顶点排序元素& b = *((S_凸边顶点排序元素*)中间->ptr_userData);
			S_凸边顶点排序元素& c = *((S_凸边顶点排序元素*)右边->ptr_userData);

			bool f = f_面朝向(point[a.ID], point[b.ID], point[c.ID]);
			if (f) {
				f_core_list_erase(排序顶点, 中间, f_释放顶点排序数据);
				当前排序顶点 = 右边;
				跳出 = false;
			}
			else {
				当前排序顶点 = 当前排序顶点->ptr_尾;
			}
		}
		
		if (跳出) break;
		
	}


	DEF_FOR_LIST(当前排序顶点, 排序顶点->ptr_item) {
		f_凸边_添加顶点(cv, point[(*((S_凸边顶点排序元素*)当前排序顶点->ptr_userData)).ID]);
	}
	vec2 p = point[(*((S_凸边顶点排序元素*)(排序顶点->ptr_item->ptr_userData))).ID];
	f_core_array_push_back((S_Array*)cv, (uint8*)&p);
	
	f_core_list_free_data(排序顶点, f_释放顶点排序数据);
	f_core_releaseList(排序顶点);

	return cv->count;
}



void f_凸边顶点排序_排序(S_凸包顶点排序* cv) {
	f_core_array_sort((S_Array*)cv, (fn_array_sort)on_凸边顶点排序_排序);
}









